(* Exercise 1.1b *)
type key = string;

(* illustrate inner structures -- pairs *)
datatype 'a tree = LEAF
		 | TREE of 'a tree * (key * 'a) * 'a tree;
	 
val empty = LEAF;  

(* illustrate String.compare *)
val rec insert : 'a tree * key * 'a -> 'a tree =
 fn (LEAF, k', v') => TREE (empty, (k', v'), empty)
  | (TREE (l, (k, v), r), k', v') => case String.compare (k', k)
				      of LESS => TREE (insert (l, k', v'), (k, v), r)
				       | EQUAL => TREE (l, (k', v'), r)
				       | MORE => TREE (l, (k, v), insert (r, k', v'));

(* a NotFound is raised if a key cannot be looked up *)
exception NotFound of key;
	  
(* lookup -- locate value bound to a key in the binary search tree
             raise pervasive exception NotFound if not present     *)
val rec lookup : ('a tree * key) -> 'a =
 fn (LEAF, k') => raise (NotFound k')
  | (TREE (l, (k, v), r), k') => case String.compare (k', k)
				  of LESS => lookup (l, k')
				   | EQUAL => v
				   | MORE => lookup (r, k');

(* testing *)
(* illustrate pattern matching *)
fun op ++ ((k, v), t) = insert (t, k, v);

infix ++;

val t1 = empty;
val t2 = ("A", 1) ++ t1;
val t3 = ("B", 2) ++ t2;
val t4 = ("C", 3) ++ t3;
val t5 = ("A", 4) ++ t4;

use "assert.sml";
    
assert (0 = (lookup (t1, "A") handle (NotFound _) => 0), "A1");
assert (1 = (lookup (t2, "A")), "A2");
assert (1 = (lookup (t3, "A")), "A3");
assert (1 = (lookup (t4, "A")), "A4");
assert (4 = (lookup (t5, "A")), "A5");

assert (0 = (lookup (t1, "B") handle (NotFound _) => 0), "B1");
assert (0 = (lookup (t2, "B") handle (NotFound _) => 0), "B2");
assert (2 = (lookup (t3, "B")), "B3");
assert (2 = (lookup (t4, "B")), "B4");
assert (2 = (lookup (t5, "B")), "B5");

assert (0 = (lookup (t1, "C") handle (NotFound _) => 0), "C1");
assert (0 = (lookup (t2, "C") handle (NotFound _) => 0), "C2");
assert (0 = (lookup (t3, "C") handle (NotFound _) => 0), "C3");
assert (3 = (lookup (t4, "C")), "C4");
assert (3 = (lookup (t5, "C")), "C5");
